home *** CD-ROM | disk | FTP | other *** search
/ MacWorld 1999 November / Macworld (1999-11).dmg / Updaters / WhiteCap 3.0.4 / WhiteCap Source.sit / WhiteCap Source / Common / General Tools / Headers / XPtrList.h < prev    next >
Text File  |  1999-07-13  |  4KB  |  117 lines
  1. #ifndef _XPTRLIST_
  2. #define _XPTRLIST_
  3.  
  4. // By Andrew O'Meara
  5.  
  6. #include "UtilStr.h"
  7.  
  8. // Post:    Returns a num >= 0 iff the first arg is less than or equal to the second arg.
  9. //            Returns a num < 0 iff the first arg is greater than the second arg.
  10. typedef int (*CompFunctionT)(const void*, const void*);
  11.  
  12.  
  13. enum ListOrderingT {
  14.     cOrderImportant,
  15.     cOrderNotImportant,
  16.     cSortLowToHigh,
  17.     cSortHighToLow
  18. };
  19.  
  20. class XPtrList : protected UtilStr {
  21.  
  22.         friend class XPtrList;
  23.         friend class XStrList;
  24.         friend class XDictionary;
  25.         friend class Hashtable;
  26.         friend class XFloatList;
  27.         friend class XLongList;
  28.     
  29.     public:
  30.                                 XPtrList( const XPtrList& inList );
  31.                                 XPtrList( ListOrderingT inOrdering = cOrderNotImportant );
  32.                                 
  33.         //    Post:    Assigns this from <inList>.
  34.         void                    Assign( const XPtrList& inList );
  35.         
  36.         //    Post:    Adds the ptr to this' list
  37.         //    Order:    O( 1 ), O( log n ) if sorting is on.
  38.         //    Note:    Returns what index the new element occupies (1-based indexing).
  39.         long                    Add( const void* inPtrToAdd );
  40.         
  41.         //    Post:    Adds the ptr to this' list after (existing) ptr number inN--make inN 0 if you want your ptr to be the 1st element
  42.         //    Order:    O( 1 )
  43.         //    Note:    If inN is invalid, the closest element is used
  44.         void                    Add( const void* inPtrToAdd, long inN );
  45.         
  46.         //    Post:    Adds each element of the incoming list to this list.  This is functionally the same as
  47.         //            looping thru the size of inPtrList and calling this.Add() for each element.
  48.         void                    Add( const XPtrList& inPtrList );
  49.         
  50.         //    Post:    Searches for the ptr in the list and removes it if found.
  51.         //    Note:    <true> is returned if the ptr was found (and removed)
  52.         //    Order:    O( N ), O( log n + alpha n ) if sorting is on.
  53.         bool                    Remove( const void* inPtrToRemove );
  54.  
  55.         //    Note:    <true> is returned if the element was found (and removed)
  56.         //    Order:    O( N ), O( log n ) if sorting is on.
  57.         //    Note:    When order is set to be preserved (via cOrderImportant or a specificed sort fcn), elements
  58.         //            at the end of the list are removed faster
  59.         bool                    RemoveElement( long inIndex );
  60.         bool                    RemoveLast();
  61.         
  62.         //    Post:    Empties the ptr list
  63.         void                    RemoveAll();
  64.         
  65.         //    Post:    Used to fetch any given ptr. If the index exists, <true> is returned and the ptr is copied to *inPtrDest.
  66.         //    Note:    One based indexing is used
  67.         //    Order:    O( 1 )
  68.         void*                    Fetch( long inIndex ) const;
  69.         bool                    Fetch( long inIndex, void** ioPtrDest ) const; 
  70.         inline bool                FetchLast( void** ioPtrDest ) const                                    { return Fetch( Count(), ioPtrDest );            }
  71.  
  72.         //     Allows easy dynamic array usage.  Simple use any index and XPtrList will expand to meet that size.
  73.         //    Impt:    Zero based indexing is used here!! (In contrast to Fetch())
  74.         //    Note:    Elements that are newly accessed are initialized to NULL
  75.         //    Note:    Indexs below 0 lead to sDummy;
  76.         //    Note:    Since caller has access to changes values, any current sorting fcn is not used
  77.         void*&                    operator[] ( const long inIndex );            
  78.         
  79.         //    Post:    Moves element at <inIndex> so that it has index 1.
  80.         void                    MoveToHead( long inIndex );
  81.         
  82.         //    Post:    Searches for the given ptr in its ptr list and returns the index of the match
  83.         //            If the item cannot be found, 0 is returned
  84.         //    Note:    One based indexing is used
  85.         //    Order:    O( N ), O( log n ) if sorting is on.
  86.         long                    FindIndexOf( const void* inMatchPtr ) const;
  87.         
  88.         //    Post:    Returns the number of items in this list.
  89.         //    Order:    O( 1 )
  90.         inline long                Count() const                                                        { return length() / 4;        }
  91.         
  92.         //    Post:    All ptrs in this list are randomly reordered.
  93.         void                    Randomize();
  94.             
  95.         //    Allows the compare fcn to be set.  Causes the current contents to be removed.
  96.         void                    SetCompFcn( CompFunctionT inFcn, bool inSortLowToHigh );
  97.         
  98.     protected:
  99.  
  100.         
  101.         ListOrderingT            mOrdering;
  102.         CompFunctionT            mCompFcn;
  103.         
  104.         //    Pre:    The list of nums must be sorted
  105.         //    Post:    Returns the (one based) index of the predicessor of <inNum>.  If zero is returned,
  106.         //            then <inNum> is <= than all the elements in the list.
  107.         long                    FetchPredIndex( const void* inNum ) const;
  108.         
  109.         static void*            sDummy;
  110.  
  111. };
  112.  
  113.  
  114.  
  115.  
  116.  
  117. #endif